# 先写O(n^2)的算法，，详解见C语言的题解
'''
n = int(input())
a = [*map(int, input().split())]
dp = [1] * n
ans = 1
for i in range(n):
    for j in range(i):
        if a[j] >= a[i] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
for i in range(n - 1, -1, -1):
    tmp, dp[i] = dp[i], 1
    for j in range(n - 1, i, -1):
        if a[j] >= a[i] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
    ans = max(ans, dp[i] + tmp - 1)
print(n - ans)
'''
# 真的还要写O(nlogn)的吗。。我都想自己写二分查找方法了。。
def new_search(a, l, r, x):
    while l < r:
        m = (l + r) // 2
        # print(l, r, m, a[m])
        # 如果当前找到的比x大或等于，就在右边找
        if a[m] >= x: l = m + 1
        else: r = m
    return r
# 恩，有了昨天java的经验，今天再随便瞎写好像快一点了，快试试这个是怎么查的吧！
'''
a = [5, 5, 4, 2, 2, 1, 1]
print(len(a))
while True:
    x = int(input())
    print(new_search(a, 0, len(a), x))
好像和昨天java写出来那个一样了，就先试试吧！
'''
n = int(input())
a = [*map(int, input().split())]
dp, ans, l = [100001], [], 0
for i in a:
    if dp[-1] >= i:
        l += 1
        dp.append(i)
        ans.append(l)
    else:
        j = new_search(dp, 0, l, i)
        dp[j] = i
        ans.append(j)
# print(dp, ans) # 应该是对的！
dp, l, wer = [100001], 0, 1
for i in range(n - 1, -1, -1):
    ai = a[i]
    if dp[-1] >= ai:
        l += 1
        dp.append(ai)
        wer = max(wer, ans[i] + l - 1)
    else:
        j = new_search(dp, 0, l, ai)
        dp[j] = ai
        wer = max(wer, ans[i] + j - 1)
print(n - wer)
# 真的挺有成就感的，手写二分查找来优化算法，然后成功了！
# 感觉就跟自己手写了stl的set,map一样23333
# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。

# IDLE是下载Python时自带的，在按住win+s搜索IDLE就能搜到了。

# 然后点左上角的File可以创建新文件，然后按F5可以运行。
